



cross_num=8000



class Game:
    def __init__(self):
        self.street=[[-1 for i in range(8000)] for j in range(8000)]
        self.streetInit()
        self.street[415][5545]=-1

    # 初始化街道数据
    def streetInit(self):
        print("------------ begin street init -----------------")
        index = -1
        with open("streets.txt",'r') as f:
            for js in f.readlines():
                index += 1
                if index==0:
                    continue
                s=js.split(',')
                x=int(s[1])
                y=int(s[2])
                len=int(s[3])
                self.street[x][y]=len

    #min road cost
    def find_new_path(self,begin,end):
        final=[-1 for i in range(cross_num)]
        to=[-1 for i in range(cross_num)]
        vis=[0 for i in range(cross_num)]
        final[begin]=0
        vis[begin]=1
        for i in range(cross_num):
            if self.street[begin][i]!=-1:
                if final[i]==-1 or final[i]>self.street[begin][i]:
                    final[i]=self.street[begin][i]
                    to[i]=begin

        for i in range(cross_num-1):
            mini=9999999
            m_j=-1
            for j in range(cross_num):
                if vis[j]==0 and final[j]!=-1 and final[j]<mini:
                    mini=final[j]
                    m_j=j
            if j==-1:
                break
            vis[m_j]=1
            for j in range(cross_num):
                if vis[j]==0 and self.street[m_j][j]!=-1 and (final[j]==-1 or final[j]>final[m_j]+self.street[m_j][j]):
                    final[j]=final[m_j]+self.street[m_j][j]
                    to[j]=m_j

        if final[end]==-1:
            return []

        path_r=[]
        node=end
        print('find path')
        while True:
            path_r.append(node)
            node=to[node]
            if node==begin:
                path_r.append(begin)
                break
        path=[ele for ele in reversed(path_r)]
        return path

def int_to_str(i):
    x=[]
    if i==0:
        x.append('a')
    while i>0:
        k=i%10
        i//=10
        x.append(chr(int(k)+ord('a')))
    s=''
    for i in x:
        s=s+i

    s=''.join(reversed(s))
    return s

if __name__=='__main__':
    game=Game()
    print('----------------')
    x=game.find_new_path(415,1749)
    p=''
    for i in range(1,len(x)):
        p+=int_to_str(x[i-1])+'-'+int_to_str(x[i])+','
    print(p)
    x=game.find_new_path(415, 2337)
    p = ''
    for i in range(1, len(x)):
        p += int_to_str(x[i - 1]) + '-' + int_to_str(x[i]) + ','
    print(p)
    x=game.find_new_path(415, 1957)
    p = ''
    for i in range(1, len(x)):
        p += int_to_str(x[i - 1]) + '-' + int_to_str(x[i]) + ','
    print(p)


